/**
 * Copyright (C) 2002 Michael Green <mtgreen@cs.ucsd.edu>
 * 
 * Copyright (C) 2002 Paul Kube <kube@cs.ucsd.edu>
 * 
 * Copyright (C) 2005 Owen Astrachan <ola@cs.duke.edu>
 * 
 * Copyright (C) 2011 Hoa Long Tam <hoalong.tam@berkeley.edu> and Armin Samii
 * <samii@berkeley.edu>
 * 
 * This file is part of CS Boggle.
 * 
 * CS Boggle is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
 * CS Boggle is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * CS boggle. If not, see <http://www.gnu.org/licenses/>.
 */

import java.util.*;

public class LexiconTrie implements LexiconInterface {
	
	private PrefixNode[] myTopLevel;
	private ArrayList<Character> loadedLetters;
	
	/**
	 * Constructor for LexiconTrie class.
	 * When called, creates 26 prefixNodes, each with a letter of the alphabet.
	 * Loads them into the myTopLevel array.
	 */
	public LexiconTrie() {
		loadedLetters = new ArrayList<Character>();
		                         
		
		PrefixNode a = new PrefixNode('a');
		PrefixNode b = new PrefixNode('b');
		PrefixNode c = new PrefixNode('c');
		PrefixNode d = new PrefixNode('d');
		PrefixNode e = new PrefixNode('e');
		PrefixNode f = new PrefixNode('f');
		PrefixNode g = new PrefixNode('g');
		PrefixNode h = new PrefixNode('h');
		PrefixNode i = new PrefixNode('i');
		PrefixNode j = new PrefixNode('j');
		PrefixNode k = new PrefixNode('k');
		PrefixNode l = new PrefixNode('l');
		PrefixNode m = new PrefixNode('m');
		PrefixNode n = new PrefixNode('n');
		PrefixNode o = new PrefixNode('o');
		PrefixNode p = new PrefixNode('p');
		PrefixNode q = new PrefixNode('q');
		PrefixNode r = new PrefixNode('r');
		PrefixNode s = new PrefixNode('s');
		PrefixNode t = new PrefixNode('t');
		PrefixNode u = new PrefixNode('u');
		PrefixNode v = new PrefixNode('v');
		PrefixNode w = new PrefixNode('w');
		PrefixNode x = new PrefixNode('x');
		PrefixNode y = new PrefixNode('y');
		PrefixNode z = new PrefixNode('z');
		
		PrefixNode[] alphabet = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z};
		myTopLevel = alphabet;
		
	}
	
	/**
	 * Returns the prefixNode from myTopLevel that shares the same myChar value of word's
	 * first letter.
	 *
	 * @param word String passed to find appropriate prefixNode
	 */
	private PrefixNode topLevelFinder(String word) {
		char firstLetter = word.charAt(0);
		switch (firstLetter) {
		case 'a':
			return myTopLevel[0];
		case 'b':
			return myTopLevel[1];		
		case 'c':
			return myTopLevel[2];
		case 'd':
			return myTopLevel[3];
		case 'e':
			return 	myTopLevel[4];
		case 'f':
			return myTopLevel[5];
		case 'g':
			return myTopLevel[6];
		case 'h':
			return myTopLevel[7];
		case 'i':	
			return myTopLevel[8];
		case 'j':	
			return myTopLevel[9];
		case 'k':
			return myTopLevel[10];
		case 'l':
			return myTopLevel[11];
		case 'm':	
			return myTopLevel[12];
		case 'n':	
			return myTopLevel[13];
		case 'o':	
			return myTopLevel[14];
		case 'p':
			return myTopLevel[15];
		case 'q':
			return myTopLevel[16];
		case 'r':
			return myTopLevel[17];
		case 's':
			return myTopLevel[18];
		case 't':				
			return myTopLevel[19];
		case 'u':
			return myTopLevel[20];
		case 'v':
			return myTopLevel[21];
		case 'w':
			return myTopLevel[22];
		case 'x':	
			return myTopLevel[23];
		case 'y':
			return myTopLevel[24];
		case 'z':
			return myTopLevel[25];
		}
		throw new IllegalArgumentException("String argument's first letter is an invalid character");
	}
	
	/**
	 * Test method for topLevelFinder. This method is called by
	 * the JUnit file through the public method LexiconTrie.privateMethodsWork().
	 */
	private static boolean topLevelFinderworks() {
		LexiconTrie l = new LexiconTrie();
		boolean test1 = (l.myTopLevel[0].equals(l.topLevelFinder("apple")));
		boolean test2 = (l.myTopLevel[3].equals(l.topLevelFinder("dense")));
		boolean test3 = (l.myTopLevel[23].equals(l.topLevelFinder("xeno")));
		
		boolean test4 = false;
		
		try{
			l.topLevelFinder("    ");
		} catch (IllegalArgumentException e) {
			test4 = true;
		}
		
		return test1 && test2 && test3 && test4;
	}
	
	/**
	 * initialInsert is called by the load method. This calls topLevelFinder to do the following: 
	 * It checks the first letter of word and matches it with the myTopLevel alphabet array. It 
	 * will then reference the appropriate prefixNode and passes the entire string but the first
	 * letter to the insertion method. For example, if the word is "apple", initialInsert will call 
	 * the prefixNode in myTopLevel that represents "a" and pass on the string "pple". 
	 * 
	 * @param word A string object of a word read from the provided text file.
	 */
	private void initialInsert(String word) {
		if (word.length() == 0) {
			return;
		}
		
		if (!loadedLetters.contains(word.charAt(0))) {
			loadedLetters.add(word.charAt(0));
		}
			
		if (word.length() == 1) {
        	insertSingleLetterWord(word);
        } else {
        	PrefixNode top = topLevelFinder(word);
        	top.insertion(word.substring(1));		
        }
	}
	
	/**
	 * Test method for initialInsertWorks. This method is called by
	 * the JUnit file through the public method LexiconTrie.privateMethodsWork().
	 */
	private static boolean initialInsertWorks() {
		LexiconTrie l = new LexiconTrie();
		
		boolean test1 = true;
		
		try{
			l.initialInsert("");
		} catch (Exception e) {
			test1 = false;
		}
		
		boolean test2 = false;
		l.initialInsert("apple");
		if (l.loadedLetters.contains('a')) {
			test2 = true;
		}
		
		boolean test3 = false;
		l.initialInsert("university");
		if (l.contains("university")); {
			test3 = true;
		}
		
		return test1 && test2 && test3;
	}
	
	/**
	 * insertSingleLetterWord is called by initialInsert if the word read from the file is a single letter.
	 * Using topLevelFinder, it references the right node and set's their isWord flag boolean to true.
	 * 
	 * @param word A string object that should be a single letter.
	 */
	private void insertSingleLetterWord(String word) {
		if (word.length() != 1) {
			return;
		}
		
		PrefixNode node = topLevelFinder(word);
		node.isWord = true;
	}
	
	/**
	 * Test method for insertSingleLetterWord. This method is called by
	 * the JUnit file through the public method LexiconTrie.privateMethodsWork().
	 */
	private static boolean insertSingleLetterWordWorks() {
		LexiconTrie l = new LexiconTrie();
		l.insertSingleLetterWord("h");
		l.insertSingleLetterWord("z");
		l.insertSingleLetterWord("c");

		return !l.contains("d") && l.contains("h") && l.contains("z") && l.contains("c");
	}
	
	/**
	 * Takes the initial prefix being checked and, based on the first letter,
	 * calls the appropriate prefixNode's stringSequenceFinder method with the same
	 * string except for the first letter.
	 * 
	 * @param prefix The prefix being checked for existence
	 * @return True if the prefix exists, false otherwise.
	 */
	private boolean hasPrefix(String prefix) {
		if (prefix.length() == 0) {
			return false;
		} else if (prefix.length() == 1) {
			char letter = prefix.charAt(0);
			return loadedLetters.contains(letter);
		}
		
		PrefixNode topPrefixNode = topLevelFinder(prefix);
		PrefixNode result = topPrefixNode.stringSequenceFinder(prefix.substring(1));
		
		if (result != null) {
			return true;
		} else {
			return false;
		}
	}
	
	/**
	 * Test method for hasPrefix. This method is called by
	 * the JUnit file through the public method LexiconTrie.privateMethodsWork().
	 */
	private static boolean hasPrefixWorks() {
		LexiconTrie l = new LexiconTrie();
		l.initialInsert("apple");
		l.initialInsert("computer");
		l.initialInsert("program");
		
		boolean test1 = l.hasPrefix("prg");
		boolean test2 = l.hasPrefix("ppl");
		
		return !test1 && !test2 && l.hasPrefix("appl") && l.hasPrefix("com") && l.hasPrefix("program"); 
	}
	
	/**
	 * Takes the initial word being checked and, based on the first letter,
	 * calls the appropriate prefixNode's stringSequenceFinder method with the
	 * same string except for the first letter.
	 * 
	 * @param word The word being checked for existence
	 * @return True if the word exists, false otherwise.
	 */
	private boolean hasWord(String word) {
		if (word.length() == 0) {
			return false;
		} else if (word.length() == 1) {
			return topLevelFinder(word).isWord;
		}
		
		PrefixNode topPrefixNode = topLevelFinder(word);
		PrefixNode result = topPrefixNode.stringSequenceFinder(word.substring(1));
		
		if (result != null && result.isWord) {
			return true;
		} else {
			return false;
		}
	}
	
	/**
	 * Test method for hasWord. This method is called by
	 * the JUnit file through the public method LexiconTrie.privateMethodsWork().
	 */
	private static boolean hasWordWorks() {
		LexiconTrie l = new LexiconTrie();
		l.initialInsert("apple");
		l.initialInsert("computer");
		l.initialInsert("program");
		
		boolean test1 = l.hasWord("prog");
		boolean test2 = l.hasWord("appl");
		
		return !test1 && !test2 && l.hasWord("apple") && l.hasWord("computer") && l.hasWord("program"); 
	}
	
	/**
	 * Nested class prefixNode. 
	 * This is the inner implementation of the Trie structure. It is analogous to the Amoeba class for
	 * AmoebaFamily structure and the TreeNode class for the BinaryTree structure. Each prefixNode
	 * has a three fields: a character 'myChar', a boolean flag 'isWord', and an ArrayList 'myChildren'.
	 * The  ArrayList implementation of the prefixNode's children is structured from the Amoeba 
	 * implementation. myChar is the character value represented by the prefixNode. isWord is set to 
	 * false unless the string of letters from myTopLevel myChar value to the the prefixNode's myChar
	 * value represents both a word and a prefix for another node. myChildren holds all references to 
	 * prefixNode's children.
	 *
	 */
	private class PrefixNode {
		private char myChar;
		private boolean isWord;
		private ArrayList<PrefixNode> myChildren;
		
		/**
		 * prefixNode constructor.
		 * Sets myChar value to value of letter and value of isWord to value of word.
		 * 
		 * @param letter Character value of new prefixNode object.
		 * @param word Boolean value of new prefixNode object.
		 */
		public PrefixNode(char letter, boolean word) {
			myChar = letter;
			isWord = word;
			myChildren = new ArrayList<PrefixNode>();
		}
		
		/**
		 * prefixNode constructor with an unspecified boolean value for word.
		 * Sets myChar value to value of letter and value of isWord is set to false.
		 * 
		 * @param letter Character value of new prefixNode object.
		 * @param word Boolean value of new prefixNode object.
		 */
		public PrefixNode(char letter) {
			myChar = letter;
			isWord = false;
			myChildren = new ArrayList<PrefixNode>();
		}
		
		/**
		 * Called when attempting to print out a prefixNode object. 
		 * Useful for debugging.
		 */
		public String toString() {
			return Character.toString(myChar);
		}
		
		
		/**
		 * Given a character value, checks if any children prefixNodes has that character value.
		 * 
		 * @param letter Character to be searched 
		 * @return Returns true if it finds a child with same character value. Otherwise, returns false.
		 */
		private boolean hasChild(char letter) {
			Iterator<PrefixNode> iter = this.myChildren.iterator();
			while (iter.hasNext()) {
				if (iter.next().myChar == letter) {
					return true;
				}
			}
			return false;
		}
		
		/**
		 * Takes a String and returns the PrefixNode that represents the last character of the string.
		 * 
		 * @param sequence 
		 * @return PrefixNode Returns the PrefixNode that represents the last character of the string
		 *                    If the word is not in the lexicon, returns null.
		 */
		private PrefixNode stringSequenceFinder(String sequence) {
			char firstLetter = sequence.charAt(0);
			
			if (hasChild(firstLetter)) {
				if (sequence.length() == 1) {
					return getChild(firstLetter);
				}
				
				PrefixNode nextNode = getChild(firstLetter);
				return nextNode.stringSequenceFinder(sequence.substring(1));
			} else {
				return null;
			}
		}
		
		/**
		 * Given a character value, it searches the ArrayList of children prefixNodes 
		 * for a prefixNode that has an equal myChar value.
		 * 
		 * @param letter
		 * @return The prefixNode that holds the same character value.
		 * 
		 */ 
		private PrefixNode getChild(char letter) {
			Iterator<PrefixNode> iter = this.myChildren.iterator();
			while (iter.hasNext()) {
				PrefixNode current = iter.next();
				if (current.myChar == letter) {
					return current;
				}
			}
			return null;
		}
		       
		/**
		 * This method is called my the initialInsertion method. If the prefixNode has a 
		 * child with myChar value equal to the first letter of word,  insertion is called 
		 * again by that child node and "word" without the first letter is passed. If the 
		 * child has the letter but the length of the entire word is 1, that means we are 
		 * trying to add a word that is already in the structure. If the prefixNode
		 * 
		 * @param word String that is being added into lexicon.
		 */
		private void insertion(String word) {
			char frontLetter = word.charAt(0);
			
			if (hasChild(frontLetter)) {
				if (word.length() == 1) {
					return;
				}
				PrefixNode nextNode = getChild(frontLetter);
				nextNode.insertion(word.substring(1));
			} else {
				addChild(word);
			}
		}
		
		/**
		 * Takes a string "word". If the length of the word is a single letter, this 
		 * must be the final letter of the word we load. This creates the final prefixNode
		 * with the myChar value being the final letter and setting the flag to be true.
		 * If the string is longer than one, create a prefixNode of the first letter and
		 * call addChild again with that child and the 
		 * 
		 * @param word
		 */
		private void addChild(String word) {
			if (word.length() == 0) {         //not sure if this can possibly be true
				return;
			} else if (word.length() == 1) {
				char letter = word.charAt(0);
				PrefixNode child = new PrefixNode(letter, true);
				myChildren.add(child);
			} else {
				char letter = word.charAt(0);
				PrefixNode child = new PrefixNode(letter, false);
				myChildren.add(child);
				child.addChild(word.substring(1));	
			}
		}
		
		
		
	} //End of the nested static class prefixNode.
	
	
	//Beginning of LexiconInterface method implementations.
	/**
	 * Load the words from an input source and store them in this lexicon.
	 * 
	 * @param input A scanner that will provide the entire dictionary.
	 */
    public void load(Scanner input) {
        while (input.hasNext()) {
            String nextStr = input.next();  
            initialInsert(nextStr);
        }
    }
    
    /**
     * If the prefix is in the lexicon, returns true.
     * 
     * @param s The word to search for.
     * @return True if the lexicon contains s.
     */
    public boolean containsPrefix(String s) {
    	return hasPrefix(s);
    }
    
    /**
     * If the word is in the lexicon, returns true.
     * 
     * @param s The word to search for.
     * @return True if the lexicon contains s.
     */
    public boolean contains(String s) {
    	return hasWord(s);
    }
    
    /**
     * Told by TA Armin on July 20, during lab section 103 that we are not
     * required to build an iterator. Reasons for this included are additional
     * hash table structure and the ability, although inefficient, to reload
     * the text file when necessary for the Part 3 implementations.
     */
    public Iterator<String> iterator() {
    	return null;
    } //End of LexiconInterface method implementations.
    
    /**
	 * This method provides JUnit access to the testing methods
	 * for private helper functions.
	 */
    public static boolean privateMethodsWork() {
    	if (!LexiconTrie.topLevelFinderworks()) {
    		return false;
    	}
    	
    	if (!LexiconTrie.initialInsertWorks()) {
    		return false;
    	}
    	
    	if (!LexiconTrie.insertSingleLetterWordWorks()) {
    		return false;
    	}
    	
    	if (!LexiconTrie.hasPrefixWorks()) {
    		return false;
    	}
    	
    	if (!LexiconTrie.hasWordWorks()) {
    		return false;
    	}
    
    	
    	if (!LexiconTrie.addChildWorks()) {
    		return false;
    	}
    	
    	if (!LexiconTrie.hasChildWorks()) {
    		return false;
    	}
    
    	if (!LexiconTrie.getChildWorks()) {
    		return false;
    	}
    	
    	if (!LexiconTrie.insertionWorks()) {
    		return false;
    	}
    	
    	if(!LexiconTrie.stringSequenceFinderWorks()) {
    		return false;
    	}
    	
    	return true;
    }
    
    /**
	 * Test method for stringSequenceFinder. This method is called by
	 * the JUnit file through the public method LexiconTrie.privateMethodsWork().
	 */
    private static boolean stringSequenceFinderWorks() {
		LexiconTrie l = new LexiconTrie();
		l.myTopLevel[0].insertion("pple");
		l.myTopLevel[1].insertion("edroom");
		l.myTopLevel[2].insertion("at");
		l.myTopLevel[3].insertion("orm");
		
		PrefixNode test1 = l.myTopLevel[0].stringSequenceFinder("pple"); 
		PrefixNode test2 = l.myTopLevel[1].stringSequenceFinder("edroom");
		PrefixNode test3 = l.myTopLevel[2].stringSequenceFinder("at");
		PrefixNode test4 = l.myTopLevel[3].stringSequenceFinder("orm");
		PrefixNode test5 = l.myTopLevel[20].stringSequenceFinder("kalamazoo");
		
		boolean result = test1 != null && test2 != null && test3 != null && test4 != null && test5 == null; 
		return result;
	}
    
    /**
	 * Test method for insertion. This method is called by
	 * the JUnit file through the public method LexiconTrie.privateMethodsWork().
	 */
    private static boolean insertionWorks() {
		LexiconTrie l = new LexiconTrie();
		l.myTopLevel[0].insertion("pple");
		l.myTopLevel[1].insertion("edroom");
		l.myTopLevel[2].insertion("at");
		l.myTopLevel[3].insertion("orm");
		
		boolean test1 = l.contains("apple");  
		boolean test2 = l.contains("bedroom");
		boolean test3 = l.contains("cat");
		boolean test4 = l.contains("dorm");
		
		return test1 && test2 & test3 & test4;
	}
	
    /**
	 * Test method for getChild. This method is called by
	 * the JUnit file through the public method LexiconTrie.privateMethodsWork().
	 */
    private static boolean getChildWorks() {
		LexiconTrie l = new LexiconTrie();
		PrefixNode aNode = l.new PrefixNode('a');
		
		aNode.addChild("a");
		aNode.addChild("b");
		
		return aNode.getChild('a').myChar == 'a' && aNode.getChild('b').myChar == 'b' && aNode.getChild('x') == null;
			

	}
    
    /**
	 * Test method for hasChild. This method is called by
	 * the JUnit file through the public method LexiconTrie.privateMethodsWork().
	 */
    private static boolean hasChildWorks() {
    	LexiconTrie l = new LexiconTrie();
		PrefixNode pNodeA = l.new PrefixNode('a');
		PrefixNode pNodeB = l.new PrefixNode('b');
		
		boolean test1 = false;
		if (!pNodeA.hasChild('n')) {
			test1 = true;
		}
		pNodeA.addChild("n");
		if (!pNodeA.hasChild('n')) {
			test1 = false;
		}
		
		boolean test2 = false;
		pNodeB.addChild("c");
		if (pNodeB.hasChild('c')) {
			test2 = true;
		}

		return test1 && test2 && !pNodeB.hasChild('n');
	}
    
    /**
	 * Test method for addChild. This method is called by
	 * the JUnit file through the public method LexiconTrie.privateMethodsWork().
	 */
    private static boolean addChildWorks() {
    	LexiconTrie l = new LexiconTrie();
		PrefixNode pNodeA = l.new PrefixNode('a');
		PrefixNode pNodeB = l.new PrefixNode('b');
		
		boolean test1 = false;
		if (!pNodeA.hasChild('n')) {
			test1 = true;
		}
		pNodeA.addChild("n");
		if (!pNodeA.hasChild('n')) {
			test1 = false;
		}
		
		boolean test2 = false;
		pNodeB.addChild("c");
		if (pNodeB.hasChild('c')) {
			test2 = true;
		}

		return test1 && test2 && !pNodeB.hasChild('n');
	}
    
} 
